Skip to main content

第26章 枚举算法

枚举算法（也叫穷举算法），核心思路是遍历问题所有合法候选解，逐个校验条件，筛选出符合要求的答案。依靠计算机高速循环遍历，逻辑简单易懂，适合解空间范围较小的题目。

26.1 枚举核心思想与执行步骤​

核心思想​

不做复杂数学推导，把所有可能的解全部列举出来，逐一判断是否满足题目约束条件，保留有效解。

标准步骤​

  1. 确定解的范围：根据题意划定上下限，缩小循环区间，减少无效遍历；
  2. 设定判断条件：写出满足答案的逻辑表达式；
  3. 循环枚举所有候选：按顺序遍历每一个可能值；
  4. 校验并收集结果：符合条件则输出/保存。

26.2 枚举优缺点​

优点​

  1. 逻辑直观，极易编写代码，新手友好；
  2. 只要范围无遗漏，一定能找出全部解，不会丢答案；
  3. 适用场景广，数字、组合类基础题都能用。

缺点​

  1. 数据范围很大时循环次数爆炸，运行缓慢；
  2. 多层嵌套枚举会大幅增加时间开销。

26.3 经典代码示例​

示例1：输出1~100所有素数​

#include <stdio.h>
#include <math.h>
int main()
{
    printf("1到100之间的素数有:\n");
    for (int num = 1; num <= 100; num++)
    {
        int isPrime = 1;
        if (num <= 1)
            isPrime = 0;
        else
        {
            for (int i = 2; i <= sqrt(num); i++)
            {
                if (num % i == 0)
                {
                    isPrime = 0;
                    break;
                }
            }
        }
        if (isPrime)
            printf("%d ", num);
    }
    return 0;
}

示例2：百钱百鸡问题​

题意：鸡翁五钱一只，鸡母三钱一只，三只鸡雏一钱，百钱买百鸡，求所有购买组合。

#include <stdio.h>
int main()
{
    int x, y, z;
    // 鸡翁最多20只
    for (x = 0; x <= 20; x++)
    {
        // 鸡母最多33只
        for (y = 0; y <= 33; y++)
        {
            z = 100 - x - y;
            if (z % 3 == 0 && 5*x + 3*y + z/3 == 100)
            {
                printf("鸡翁:%d, 鸡母:%d, 鸡雏:%d\n", x, y, z);
            }
        }
    }
    return 0;
}

示例3：1~50同时被3、5整除的数字​

#include <iostream>
using namespace std;
int main()
{
    cout << "1到50之间能同时被3和5整除的数:" << endl;
    for (int i = 1; i <= 50; i++)
    {
        if (i % 3 == 0 && i % 5 == 0)
        {
            cout << i << " ";
        }
    }
    return 0;
}

示例4：水仙花数（三位数，各位立方和等于自身）​

#include <iostream>
using namespace std;
int main()
{
    cout << "所有水仙花数:" << endl;
    for (int num = 100; num <= 999; num++)
    {
        int h = num / 100;
        int t = (num / 10) % 10;
        int u = num % 10;
        if (h*h*h + t*t*t + u*u == num)
        {
            cout << num << " ";
        }
    }
    return 0;
}

26.4 枚举优化注意事项​

  1. 精准缩小枚举边界，减少循环次数；
  2. 多层循环时，把取值范围小的变量放在外层，减少内层循环总次数；
  3. 简化判断条件，减少循环内部计算；
  4. 找到唯一解时可使用break提前终止循环，节省时间。